import Graph from "./Graph";
import {Colors, initializeColor} from "./initializeColor";
import Queue from "../queue/queue";

export function breadthFirstSearch<T>(graph: Graph<T>,startVertex:T,callback?:Function){
    const vertices = graph.getVertices();
    const adjacencyList = graph.getAdjacencyList()
    const color = initializeColor(vertices);

    const queue = new Queue<T>();
    queue.enqueue(startVertex);

    while (!queue.isEmpty()){
        // 出队
        let now_item = <T>queue.dequeue();
        // 设置为灰色
        color.set(now_item,Colors.GREY);
        // 获取当前顶点关联的顶点
        let now_adjList = <T[]>adjacencyList.get(now_item)?.value;
        // 入队
        for (let i = 0; i < now_adjList?.length; i++) {
            if (color.get(now_adjList[i]) === Colors.WHITE) {
                color.set(now_adjList[i],Colors.GREY)
                queue.enqueue(now_adjList[i]);
            }
        }
        // 设置为黑色
        color.set(now_item,Colors.BLACK);
        callback?.(now_item);
    }
}


/**
 * 广度遍历并且寻找最短路径
 * @param graph
 * @param startVertex
 * @param callback
 */
export function breadthFirstSearchAndFindMiniPath<T>(graph: Graph<T>,startVertex:T): { distances: Map<T, number>; predecessors: Map<T, T | null> } {
    const vertices = graph.getVertices();
    const adjacencyList = graph.getAdjacencyList()
    const color = initializeColor(vertices);
    const distances = new Map<T,number>(); // 记录距离
    const predecessors = new Map<T,T | null>(); // 前溯点
    for (let i = 0; i < vertices.length; i++) {
        distances.set(vertices[i],0);
        predecessors.set(vertices[i],null);
    }

    const queue = new Queue<T>();
    queue.enqueue(startVertex);

    while (!queue.isEmpty()){
        // 出队
        let now_item = <T>queue.dequeue();
        // 设置为灰色
        color.set(now_item,Colors.GREY);
        // 获取当前顶点关联的顶点
        let now_adjList = <T[]>adjacencyList.get(now_item)?.value;
        // 入队
        for (let i = 0; i < now_adjList?.length; i++) {
            if (color.get(now_adjList[i]) === Colors.WHITE) {
                color.set(now_adjList[i],Colors.GREY)
                distances.set(now_adjList[i],<number>distances.get(now_item) + 1);
                predecessors.set(now_adjList[i],now_item);
                queue.enqueue(now_adjList[i]);
            }
        }
        // 设置为黑色
        color.set(now_item,Colors.BLACK);
    }

    return {
        distances,predecessors
    }
}


const graph = new Graph<string>();
const myVertices = ["A","B","C","D","E","F","G","H","I","J","K"]
for (let i = 0; i < myVertices.length; i++) {
    graph.addVertex(myVertices[i]);
}

graph.addEdge(myVertices[0],myVertices[1])
graph.addEdge(myVertices[0],myVertices[2])
graph.addEdge(myVertices[0],myVertices[3])
graph.addEdge(myVertices[2],myVertices[6])
graph.addEdge(myVertices[3],myVertices[5])
graph.addEdge(myVertices[6],myVertices[1])

console.log(graph.toString())


console.log(breadthFirstSearchAndFindMiniPath(graph, "A"));
